package com.cat.greedyAlgorithm;

import java.util.*;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/most-profit-assigning-work/description/
 * @create 2025/8/25 08:46
 * @since JDK17
 */

public class Solution26 {
    public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
        List<Integer> list = new ArrayList<>();
        int n = difficulty.length, ans = 0, m = worker.length;
        int[] max = new int[n + 1]; // 难度前缀
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        Collections.sort(list, Comparator.comparingInt(o -> difficulty[o]));
        for (int i = 0; i < n; i++) {
            max[i + 1] = Math.max(max[i], profit[list.get(i)]);
        }
        Arrays.sort(worker);
        for (int i = 0, j = 0; i < m; i++) {   //
            while (j < n && difficulty[list.get(j)] <= worker[i]) {
                j++;
            }
            ans += max[j];
        }

        return ans;
    }
}
